'''
https://leetcode.cn/problems/maximal-rectangle/description/
'''
from collections import deque
from typing import List


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        # see problem_largest_rectangle_in_histogram
        # https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
        def largestRectangleArea(heights: List[int]) -> int:
            n = len(heights)
            ans = 0
            stack = deque()  # 栈中元素大压小 ,为了找左右比我小的位置
            for i, height in enumerate(heights):
                while stack and height <= heights[stack[-1]]:
                    cur = stack.pop()
                    # left + 1, ... right - 1， 这段区间内，nums[cur]最小值
                    left = stack[-1] if stack else -1
                    right = i
                    ans = max(ans, heights[cur] * (right - left - 1))
                stack.append(i)
            while stack:
                cur = stack.pop()
                left = stack[-1] if stack else -1
                right = n
                ans = max(ans, heights[cur] * (right - left - 1))
            return ans

        m, n = len(matrix), len(matrix[0])
        ans = 0
        # for i in range(m):
        #     heights = [0] * n
        #     for j in range(n):
        #         for k in range(i, -1, -1):
        #             if matrix[k][j] == '0': break
        #             heights[j] += 1
        #     print(heights)
        #     ans = max(ans, largestRectangleArea(heights))
        heights = [0] * n
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '0':
                    heights[j] = 0
                else:
                    heights[j] += 1
            # print(heights)
            ans = max(ans, largestRectangleArea(heights))
        return ans



